# include <stdio.h>

# define MAX 512
# define MAX_ROW 5
# define MAX_COL 5

struct point
{
  int row,col;
}stack[MAX];

int top = 0;

int maze[MAX_ROW][MAX_COL]
 ={ {0,1,0,0,0},
    {0,1,0,1,0},
    {0,0,0,0,0},
    {0,1,1,1,0},
    {0,0,0,1,0}
    };

struct point predecessor[MAX_ROW][MAX_COL] = {
    {{-1,-1}, {-1,-1}, {-1,-1}, {-1,-1}, {-1,-1}},
    {{-1,-1}, {-1,-1}, {-1,-1}, {-1,-1}, {-1,-1}},
    {{-1,-1}, {-1,-1}, {-1,-1}, {-1,-1}, {-1,-1}},
    {{-1,-1}, {-1,-1}, {-1,-1}, {-1,-1}, {-1,-1}},
    {{-1,-1}, {-1,-1}, {-1,-1}, {-1,-1}, {-1,-1}},
};
// stack operations.
void push(struct point p)
{
    stack[top++] = p;
}

struct point pop()
{
    struct point p;
    p = stack[--top];
    return p;
}

int is_empty()
{
    return top == 0;
}

int visit(int row, int col, struct point p)
{
    struct point p_curr = {row,col};
    push(p_curr);
    maze[row][col] = 2;
    predecessor[row][col] = p;
}

int main()
{
    struct point p = {0,0};
    push(p);
    maze[p.row][p.col] = 2;

    //solve_maze();
    while(!is_empty())
    {
        p = pop();
        if(p.row == MAX_ROW -1 && p.col == MAX_COL -1)
            break;
        if(p.row +1 < MAX_ROW && maze[p.row+1][p.col] == 0)
        {
            visit(p.row+1, p.col, p);
        }
        if(p.col+1  < MAX_COL && maze[p.row][p.col+1] == 0)
        {
            visit(p.row, p.col+1, p);
        }
        if(p.row -1 >= 0 && maze[p.row-1][p.col] == 0)
        {
            visit(p.row-1, p.col, p);
        }
        if(p.col-1 >= 0 && maze[p.row][p.col-1] == 0)
        {
            visit(p.row, p.col-1, p);
        }
    }

    if(p.row == MAX_ROW -1 && p.col == MAX_COL -1)
    {
        printf("(%d,%d)\n",p.row, p.col);
        while(predecessor[p.row][p.col].col != -1)
        {
            p = predecessor[p.row][p.col];
            printf("(%d,%d)\n",p.row, p.col);
        }
    }
    else
        printf("No path!\n");


    return 0;
}
